Search Results

Documents authored by Liberti, Leo

Document
DOI: 10.4230/LIPIcs.SEA.2022.21
Practical Performance of Random Projections in Linear Programming

Authors: Leo Liberti, Benedetto Manca, and Pierre-Louis Poirion

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

Abstract
The use of random projections in mathematical programming allows standard solution algorithms to solve instances of much larger sizes, at least approximately. Approximation results have been derived in the relevant literature for many specific problems, as well as for several mathematical programming subclasses. Despite the theoretical developments, it is not always clear that random projections are actually useful in solving mathematical programs in practice. In this paper we provide a computational assessment of the application of random projections to linear programming.
Cite as

Leo Liberti, Benedetto Manca, and Pierre-Louis Poirion. Practical Performance of Random Projections in Linear Programming. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{liberti_et_al:LIPIcs.SEA.2022.21,
  author =	{Liberti, Leo and Manca, Benedetto and Poirion, Pierre-Louis},
  title =	{{Practical Performance of Random Projections in Linear Programming}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.21},
  URN =		{urn:nbn:de:0030-drops-165550},
  doi =		{10.4230/LIPIcs.SEA.2022.21},
  annote =	{Keywords: Linear Programming, Johnson-Lindenstrauss Lemma, Computational testing}
}
Document
DOI: 10.4230/LIPIcs.SEA.2017.5
The Isomap Algorithm in Distance Geometry

Authors: Leo Liberti and Claudia D'Ambrosio

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
The fundamental problem of distance geometry consists in finding a realization of a given weighted graph in a Euclidean space of given dimension, in such a way that vertices are realized as points and edges as straight segments having the same lengths as their given weights. This problem arises in structural proteomics, wireless sensor networks, and clock synchronization protocols to name a few applications. The well-known Isomap method is a dimensionality reduction heuristic which projects finite but high dimensional metric spaces into the "most significant" lower dimensional ones, where significance is measured by the magnitude of the corresponding eigenvalues. We start from a simple observation, namely that Isomap can also be used to provide approximate realizations of weighted graphs very efficiently, and then derive and benchmark six new heuristics.
Cite as

Leo Liberti and Claudia D'Ambrosio. The Isomap Algorithm in Distance Geometry. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{liberti_et_al:LIPIcs.SEA.2017.5,
  author =	{Liberti, Leo and D'Ambrosio, Claudia},
  title =	{{The Isomap Algorithm in Distance Geometry}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.5},
  URN =		{urn:nbn:de:0030-drops-76079},
  doi =		{10.4230/LIPIcs.SEA.2017.5},
  annote =	{Keywords: distance geometry problem, protein conformation, heuristics}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2012
OASIcs, Volume 25, ATMOS'12, Complete Volume

Authors: Daniel Delling and Leo Liberti

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
OASIcs, Volume 25, ATMOS'12, Complete Volume
Cite as

12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Proceedings{delling_et_al:OASIcs.ATMOS.2012,
  title =	{{OASIcs, Volume 25, ATMOS'12, Complete Volume}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012},
  URN =		{urn:nbn:de:0030-drops-37255},
  doi =		{10.4230/OASIcs.ATMOS.2012},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Optimization, Graph Theory, Applications}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2012.i
Frontmatter, Table of Contents, Preface, Workshop Organization

Authors: Daniel Delling and Leo Liberti

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
Frontmatter, Table of contents, Preface, Workshop Organization
Cite as

12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. i-xi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{delling_et_al:OASIcs.ATMOS.2012.i,
  author =	{Delling, Daniel and Liberti, Leo},
  title =	{{Frontmatter, Table of Contents, Preface, Workshop Organization}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{i--xi},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.i},
  URN =		{urn:nbn:de:0030-drops-36980},
  doi =		{10.4230/OASIcs.ATMOS.2012.i},
  annote =	{Keywords: Frontmatter, Table of contents, Preface, Workshop Organization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.64
UniALT for regular language contrained shortest paths on a multi-modal transportation network

Authors: Dominik Kirchler, Leo Liberti, Thomas Pajor, and Roberto Wolfler Calvo

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
Shortest paths on road networks can be efficiently calculated using Dijkstra's algorithm (D). In addition to roads, multi-modal transportation networks include public transportation, bicycle lanes, etc. For paths on this type of network, further constraints, e.g., preferences in using certain modes of transportation, may arise. The regular language constrained shortest path problem deals with this kind of problem. It uses a regular language to model the constraints. The problem can be solved efficiently by using a generalization of Dijkstra's algorithm (D_RegLC). In this paper we propose an adaption of the speed-up technique uniALT, in order to accelerate D_RegLC. We call our algorithm SDALT. We provide experimental results on a realistic multi-modal public transportation network including time-dependent cost functions on arcs. The experiments show that our algorithm performs well, with speed-ups of a factor 2 to 20.
Cite as

Dominik Kirchler, Leo Liberti, Thomas Pajor, and Roberto Wolfler Calvo. UniALT for regular language contrained shortest paths on a multi-modal transportation network. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 64-75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{kirchler_et_al:OASIcs.ATMOS.2011.64,
  author =	{Kirchler, Dominik and Liberti, Leo and Pajor, Thomas and Wolfler Calvo, Roberto},
  title =	{{UniALT for regular language contrained shortest paths on a multi-modal transportation network}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{64--75},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.64},
  URN =		{urn:nbn:de:0030-drops-32670},
  doi =		{10.4230/OASIcs.ATMOS.2011.64},
  annote =	{Keywords: time-dependency, ALT, regular language, shortest path, multi-modal}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact